#include <stdio.h>
#include <stdlib.h> 

/**
 * 这里计划采用keys数组多一个的考虑(假设5阶)
 * 0 1 2 3 4 5 此时的0号单元不用 然后这个五号单元是为了便于分裂和合并 从1开始找起
 * 0 1 2 3 4   其实也可以用上0号单元， 这样就不用浪费空间了
*/

typedef struct Node {
    int level; //阶数
    int keyNum;//关键字数目
    int *keys;//关键字数组
    int childNum;//孩子数目
    struct Node **child;//孩子数组
    struct Node *parent;//父亲指针
} Node;

//初始化node
Node *initNode(int level)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->level = level;
    node->keyNum = 0;
    node->childNum = 0;
    node->parent = NULL;
    node->child = (Node **)malloc(sizeof(Node *) * level);
    node->keys = (int *)malloc(sizeof(int) * (level+ 1));
    int i;
    for (i = 0; i < level; i++){
        node->keys[i] = 0;
        node->child[i] = NULL;
    }
    node->keys[i] = 0;//i = level + 1
    return node;
}
int findSuiteIndex(Node *node, int data)
{
    int index;
    for (index = 1; index <= node->keyNum; index++) {
        if (data < node->keys[index])
            break; 
    }
    return index;//最坏情况返回keyNum+1;然后就可以得到下一个节点的最后那个
}

Node *findSuiteLeaf(Node *node, int data)
{
    if (node->childNum == 0) {
        return node;
    } else {
        int index = findSuiteIndex(node, data);
        return findSuiteLeaf(node->child[index-1], data);
    }
}

void addData(Node *node, int data, Node **T)
{
    //插到叶子节点上
    int index = findSuiteIndex(node, data);
    for (int i = node->keyNum; i >= index; i--) {
        node->keys[i+1] = node->keys[i];
    }
    node->keys[index] = data;
    node -> keyNum = node -> keyNum + 1;
    //判断是否要分裂
    if (node->keyNum == node->level) {
        int mid = node -> level / 2 + node -> level % 2;
        Node *lchild = initNode(node->level);
        Node *rchild = initNode(node->level);
        //复制mid左边的关键字到lchild
        for (int i = 1; i < mid; i++) {
            addData(lchild, node->keys[i], T);
        }
        //复制mid右边的关键字到rchild
        for (int i = mid+1; i <= node->keyNum; i++) {
            addData(rchild, node->keys[i], T);
        }
        //这里不是叶子节点的情况了
        //复制左右孩子
        for (int i = 0; i < mid; i++) {
            lchild->child[i] = node->child[i];
            if (node->child[i] != NULL) {
                node->child[i]->parent = lchild;
                lchild->childNum++;
            }
        }
        int index = 0;
        for (int i = mid; i < node->childNum; i++) {
            rchild->child[index++] = node->child[i];
            if (node->child[i] != NULL) {
                node->child[i]->parent = rchild;
                rchild->childNum++;
            }
        }
        //判断是否有父亲
        if (node->parent == NULL) {
            Node *newparent = initNode(node->level);
            addData(newparent, node->keys[mid], T);
            newparent->child[0] = lchild;
            newparent->child[1] = rchild;
            newparent->childNum = 2;
            lchild -> parent = newparent;
            rchild -> parent = newparent;
            *T = newparent;
        } else {
            lchild->parent = node->parent;
            rchild->parent = node->parent;
            int index = findSuiteIndex(node->parent, node->keys[mid]);
            node->parent->child[index-1] = lchild;//原来是指向node
            if (node->parent->child[index] != NULL) {
                for (int i = node->parent->childNum-1; i >= index; i--) {
                    node->parent->child[i+1] = node->parent->child[i];
                }
            }
            node->parent->child[index] = rchild;
            node->parent->childNum++;
            addData(node->parent, node->keys[mid], T);
        }
    }
}

void insert(Node** T, int data) {
    Node* node = findSuiteLeaf(*T, data);
    addData(node, data, T);
}


void printTree(Node* T) {
    if (T != NULL) {
        for (int i  = 1; i <= T -> keyNum; i++) {
            printf("%d ", T -> keys[i]);
        }
        printf("\n");
        for (int i = 0; i < T -> childNum; i++) {
            printTree(T -> child[i]);
        }
    }
} 

Node* find(Node* node, int data) {
    if (node == NULL) {
        return NULL;
    }
    for (int i = 1; i <= node -> keyNum; i++) {
        if (data == node -> keys[i]) {
            return node;
        }
        else if (data < node -> keys[i]) {
            return find(node -> child[i - 1], data);
        }
        else {
            if (i != node -> keyNum && data < node -> keys[i + 1]) 
                return find(node -> child[i], data);
        }
    }
    return find(node -> child[node -> keyNum], data);
}

int main(void)
{
    
    Node* T = initNode(5);
    insert(&T, 1);
    insert(&T, 2);
    insert(&T, 6);
    insert(&T, 7);
    insert(&T, 11);
    insert(&T, 4);
    insert(&T, 8);
    insert(&T, 13);
    insert(&T, 10);
    insert(&T, 5);
    insert(&T, 17);
    insert(&T, 9);
    insert(&T, 16);
    insert(&T, 20);
    insert(&T, 3);
    insert(&T, 12);
    insert(&T, 14);
    insert(&T, 18);
    insert(&T, 19);
    insert(&T, 15);
    printTree(T);
    
    printf("\n");
    Node* node = find(T, 7);
    if (node) {
        for (int i = 1; i <= node -> keyNum; i++) {
            printf("%d ", node -> keys[i]);
        }
        printf("\n");
    }
    
    return 0;
}